package com.javaedge.concurrency.schedule;

import lombok.extern.slf4j.Slf4j;

import java.util.concurrent.DelayQueue;

/**
 * @author apdoer
 * @version 1.0
 * @date 2021/3/22 19:31
 * 考虑这样的一个场景，当前你有1000个任务，要让这1000个任务每隔几分钟触发某个操作。要是实现这样的需求，很多人第一想法就是弄一个定时器。
 * 但是1000个任务就是1000个定时器，一个定时器是一个线程。为了解决这个问题，就出现了时间轮算法。
 * 本篇文章将为您讲述什么是时间轮算法，以及在Java中怎么用代码实现时间轮算法。
 *
 * 时间轮
 * 时间轮简介：时间轮方案将现实生活中的时钟概念引入到软件设计中，主要思路是定义一个时钟周期（比如时钟的12小时）和步长（比如时钟的一秒走一次），
 * 当指针每走一步的时候，会获取当前时钟刻度上挂载的任务并执行。
 *
 * 核心思想
 * 一个环形数组存储时间轮的所有槽(看你的手表),每个槽对应当前时间轮的最小精度
 * 超过当前时间轮最大表示范围的会被丢到上层时间轮,上层时间轮的最小精度即为下层时间轮能表达的最大时间(时分秒概念)
 * 每个槽对应一个环形链表存储该时间应该被执行的任务
 * 需要一个线程去驱动指针运转,获取到期任务
 */
@Slf4j
public class TimeWheel {
    /**
     * 一个槽的时间间隔(时间轮最小刻度)
     */
    private long tickMs;

    /**
     * 时间轮大小(槽的个数)
     */
    private int wheelSize;

    private long currentTime;

    /**
     * 槽
     */
    private TimerTaskChain[] buckets;

    /**
     * 上层时间轮
     */
    private volatile TimeWheel overflowWheel;

    /**
     * 一个timer只有一个delayqueue
     */
    private DelayQueue<TimerTaskChain> delayQueue;

    public TimeWheel(long tickMs, int wheelSize, long currentTime, DelayQueue<TimerTaskChain> delayQueue) {
        this.currentTime = currentTime - (currentTime % tickMs);
        this.tickMs = tickMs;
        this.wheelSize = wheelSize;
        this.buckets = new TimerTaskChain[wheelSize];
        this.delayQueue = delayQueue;
        for (int i = 0; i < wheelSize; i++) {
            buckets[i] = new TimerTaskChain();
        }
    }


    /**
     * 一轮的时间跨度
     */
    private long getInterval(){
        return tickMs * wheelSize;
    }

    public boolean add(TimerTaskEntry entry) {
        long expiration = entry.getExpireMs();
        if (expiration < tickMs + currentTime) {
            //到期了
            return false;
        } else if (expiration < currentTime + getInterval()) {
            //扔进当前时间轮的某个槽里,只有时间大于某个槽,才会放进去
            long virtualId = (expiration / tickMs);
            int index = (int) (virtualId % wheelSize);
            TimerTaskChain bucket = buckets[index];
            bucket.addTask(entry);
            //设置bucket 过期时间
            if (bucket.setExpiration(expiration)) {
                //设好过期时间的bucket需要入队
                delayQueue.offer(bucket);
                return true;
            }
        } else {
            //当前轮不能满足,需要扔到上一轮
            TimeWheel timeWheel = getOverflowWheel();
            return timeWheel.add(entry);
        }
        return false;
    }


    private TimeWheel getOverflowWheel() {
        if (overflowWheel == null) {
            synchronized (this) {
                if (overflowWheel == null) {
                    overflowWheel = new TimeWheel(getInterval(), wheelSize, currentTime, delayQueue);
                }
            }
        }
        return overflowWheel;
    }

    /**
     * 推进指针
     *
     * @param timestamp
     */
    public void advanceLock(long timestamp) {
        if (timestamp > currentTime + tickMs) {
            currentTime = timestamp - (timestamp % tickMs);
            if (overflowWheel != null) {
                this.getOverflowWheel().advanceLock(timestamp);
            }
        }
    }
}